﻿namespace Leetcode.N0033;
public class Solution
{
    public int Search(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right)
        {
            var i = left + (right - left) / 2;
            if (nums[i] == target)
            {
                return i;
            }
            // target和i在同一边
            if (target < nums[0] && nums[i] < nums[0] || target >= nums[0] && nums[i] >= nums[0])
            {
                if (target > nums[i])
                {
                    left = i + 1;
                }
                else
                {
                    right = i - 1;
                }
            }
            // i在左边，target在右边
            else if (target > nums[i])
            {
                right = i - 1;
            }
            // i在右边，target在左边
            else
            {
                left = i + 1;
            }
        }

        return -1;
    }
}
